package cn.fxzhang.leetcode.contest.week237;


/**
 * 5737. 所有数对按位与结果的异或和
 * 输入：arr1 = [1,2,3], arr2 = [6,5]
 * 输出：0
 * 解释：列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1] ，
 * 异或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0 。
 *提示：
 * 1 <= arr1.length, arr2.length <= 10^5
 * 0 <= arr1[i], arr2[j] <= 10^9
 *
 * 类型：数值计算
 * 题解：(a&b1)⊕(a&b2)=[(¬a∣¬b1)&(a∣b2)]∣[(¬a∣¬b2)&(a∣b1)]
 * =(¬b1&a&b2)∣(¬b2&a&b1)
 * =a&((¬b1&b2)∣(¬b2&b1))
 * =a&(b1⊕b2)
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 2 ms, 击败了100.00%
 * 内存消耗: 52 MB, 击败了100.00%
 *
 * 【困难】通过次数1,228提交次数3,723
 * @author 张晓帆
 * @date 2021/4/18
 */
public class P5737_Find_Xor_Sum_Of_All_Pairs_Bitwise_And {

    public int getXORSum(int[] arr1, int[] arr2) {
        int x = 0;
        for (int value : arr2) {
            x = x ^ value;
        }

        int ans = 0;
        for (int value : arr1) {
            ans = ans ^ (value & x);
        }
        return ans;
    }
}
